package io.gitee.wiqer.hard;

/**
 * 给出一个长度为 n 的，仅包含字符 '(' 和 ')' 的字符串，计算最长的格式正确的括号子串的长度。
 *
 * 例1: 对于字符串 "(()" 来说，最长的格式正确的子串是 "()" ，长度为 2 .
 * 例2：对于字符串 ")()())" , 来说, 最长的格式正确的子串是 "()()" ，长度为 4 .
 *
 * 字符串长度：0 \le n \le 5*10^50≤n≤5∗10
 * 5
 *
 *
 * 要求时间复杂度 O(n) ,空间复杂度 O(n).
 */
public class SolutionNC49_LongestValidParentheses {
    /**
     *
     * @param s string字符串
     * @return int整型
     */
    public int longestValidParentheses (String s) {
        // write code here
        if (s == null || s.length() < 2) {
            return 0;
        }

        int len = s.length();

        int[] dp = new int[len]; // 存储到此下标及包括下标字符在内的最大括号子串长度
        char[] ss = s.toCharArray();

        int res = 0;

        for (int i = 1; i < len; i++) {
            if (ss[i] == ')') {
                int pre = i - dp[i - 1] - 1;
                if (pre >= 0 && ss[pre] == '(') {
                    dp[i] = dp[i - 1] + 2; // 如果匹配上就+2
                    if (pre - 1 >= 0) {
                        dp[i] += dp[pre - 1]; // 还能把相邻的最长子串一起纳入，这就是dp维护到此下标包含下标最长子串的好处
                    }

                    res = Math.max(res, dp[i]); // 更新最大值
                }
            }
        }

        return res;
    }
}
